package E_2024;

import java.util.LinkedList;
import java.util.List;

/*
    有一辆汽车需要从 m*n 的地图的左上角(起点)开往地图的右下角(终点)，去往每一个地区都需要消耗一定的油量，加油站可进行加油
    请你计算汽车确保从起点到达终点时所需的最少初始油量说明:
    (1) 智能汽车可以上下左右四个方向移动1
    (2) 地图上的数字取值是 0或-1 或者正整数:
    1: 表示加油站，可以加满油，汽车的油箱容量最大为 100;
    0: 表示这个地区是障碍物，汽车不能通过
    正整数: 表示汽车走过这个地区的耗油量
    (3) 如果汽车无论如何都无法到达终点，则返回 -1
输入描述
    第一行为两个数字，M，V，表示地图的大小为 M,N(0< M,N < 200)

    后面一个M*N 的矩阵，其中的值是 0 或 -1 或正整数，加油站的总数不超过 200个
输出描述
    如果汽车无论如何都无法到达终点，则返回-1
    如果汽车可以到达终点，则返回最少的初始油量
示例1
    输入
    2,2
    10,20
    30,40
    输出
    70
 */
public class E_200_2 {
    public static void main(String[] args) {
        ans(new int[][]{{10,20},{30,40}});
        System.out.println(min);
    }
    static int min = 100;
    public static int ans(int[][] map){
        int x = map.length;
        int y = map[0].length;
        int[][] temp = new int[x][y];
        return turn(map,temp,0,0,new LinkedList<>(),100);
    }
    public static int turn(int[][] map , int[][] lj, int x , int y, List<Integer> l, int qy){
        if (x < 0 || y < 0 || x == map.length || y == map[0].length || lj[x][y] == 1 || map[x][y] == 0 || qy < map[x][y]) return 0;
        lj[x][y] = 1;
        // 记录经过的点
        l.add(map[x][y]);
        // 当到达终点后计算路径中消耗情况
        if (x == map.length -1 && y == map[0].length -1){
            int m = 0;
            for (Integer i : l) {
                if (i == -1){
                    break;
                }
                m += i;
            }
            min = Math.min(m,min);
            return 0;
        }
        // 当经过加油站时，油加满
        if (map[x][y] == -1) qy = 100;
        else qy = qy - map[x][y];
        turn(map,lj,x+1,y,l,qy);
        turn(map,lj,x-1,y,l,qy);
        turn(map,lj,x,y+1,l,qy);
        turn(map,lj,x,y-1,l,qy);
        // 当前点所有可能都经过之后，退回上一点需要将当前信息清空
        lj[x][y] = 0;
        l.remove(l.size() - 1);
        return -1;
    }
}
